﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;

namespace Raven
{
    public class SparseGraph<N, E> : IEnumerable where N : GraphNode where E : GraphEdge
    {
        //the nodes that comprise this graph
        private List<N> _nodes = new List<N>();

        //a vector of adjacency edge lists. (each node index keys into the 
        //list of edges associated with that node)
        private List<LinkedList<E>> _edges = new List<LinkedList<E>>();

        private bool _digraph;
        private int _nextNodeIndex;

        public SparseGraph(bool digraph)
        {
            _nextNodeIndex = 0;
            _digraph = digraph;
        }

        public void Clear()
        {
            _nextNodeIndex = 0;
            _nodes.Clear();
            _edges.Clear();
        }

        public int NumNodes()
        {
            return _nodes.Count;
        }

        public N GetNode(int idx)
        {
            Utility.Assert(idx < _nodes.Count && idx >= 0, "<SparseGraph::GetNode>: invalid index");
            return _nodes[idx];
        }

        public bool Load(BinaryReader stream)
        {
            Clear();
            //get the number of nodes and read them in
            int numNodes = stream.ReadInt32();
            int numEdges = 0;
            for (int n = 0; n < numNodes; ++n)
            {
                N newNode = Activator.CreateInstance(typeof(N), stream) as N;

                //when editing graphs it's possible to end up with a situation where some
                //of the nodes have been invalidated (their id's set to invalid_node_index). Therefore
                //when a node of index invalid_node_index is encountered, it must still be added.
                if (newNode.Index() != Constants.INVALID_NODE_INDEX)
                {
                    AddNode(newNode);
                }
                else
                {
                    _nodes.Add(newNode);

                    //make sure an edgelist is added for each node
                    _edges.Add(new LinkedList<E>());

                    ++_nextNodeIndex;
                }
            }

            //now add the edges
            numEdges = stream.ReadInt32();
            for (int e = 0; e < numEdges; ++e)
            {
                E nextEdge = Activator.CreateInstance(typeof(E), stream) as E;
                AddEdge(nextEdge);
            }

            return true;
        }

        public int AddNode(N node)
        {
            if (node.Index() < _nodes.Count)
            {
                //make sure the client is not trying to add a node with the same ID as
                //a currently active node
                Utility.Assert(_nodes[node.Index()].Index() == Constants.INVALID_NODE_INDEX,
                    "<SparseGraph::AddNode>: Attempting to add a node with a duplicate ID");

                _nodes[node.Index()] = node;

                return _nextNodeIndex;
            }

            else
            {
                //make sure the new node has been indexed correctly
                Utility.Assert(node.Index() == _nextNodeIndex, "<SparseGraph::AddNode>:invalid index");

                _nodes.Add(node);
                _edges.Add(new LinkedList<E>());

                return _nextNodeIndex++;
            }
        }

        public void AddEdge(E edge)
        {
            //first make sure the from and to nodes exist within the graph 
            Utility.Assert(edge.From() < _nextNodeIndex && edge.To() < _nextNodeIndex,
                "<SparseGraph::AddEdge>: invalid node index");

            //make sure both nodes are active before adding the edge
            if (_nodes[edge.To()].Index() != Constants.INVALID_NODE_INDEX &&
                _nodes[edge.From()].Index() != Constants.INVALID_NODE_INDEX)
            {
                //add the edge, first making sure it is unique
                if (UniqueEdge(edge.From(), edge.To()))
                {
                    _edges[edge.From()].AddLast(edge);
                }

                //if the graph is undirected we must add another connection in the opposite
                //direction
                if (!_digraph)
                {
                    //check to make sure the edge is unique before adding
                    if (UniqueEdge(edge.To(), edge.From()))
                    {
                        E newEdge = Activator.CreateInstance(typeof(E)) as E;

                        newEdge.SetTo(edge.From());
                        newEdge.SetFrom(edge.To());
                        newEdge.SetCost(edge.Cost());

                        _edges[edge.To()].AddLast(newEdge);
                    }
                }
            }
        }

        public bool UniqueEdge(int from, int to)
        {
            foreach (var curEdge in _edges[from])
            {
                if (curEdge.To() == to)
                {
                    return false;
                }
            }

            return true;
        }

        public Fix CalculateAverageGraphEdgeLength()
        {
            Fix TotalLength = 0;
            int NumEdgesCounted = 0;

            foreach (var node in _nodes)
            {
                foreach (var edge in _edges[node.Index()])
                {
                    //increment edge counter
                    ++NumEdgesCounted;

                    //add length of edge to total length
                    Fix l = Vector2.Distance(_nodes[edge.From()].Pos(), _nodes[edge.To()].Pos());
                    if (l.Raw < 0)
                    {
                        int end = 0;
                    }
                    TotalLength += l;
                }
            }

            return TotalLength / NumEdgesCounted;
        }

        public IEnumerator GetEnumerator()
        {
            return _nodes.GetEnumerator();
        }

        public LinkedList<E> GetEdges(int index)
        {
            return _edges[index];
        }

        //returns the number of active nodes present in the graph (this method's
        //performance can be improved greatly by caching the value)
        public int NumActiveNodes()
        {
            int count = 0;

            for (int n = 0; n < _nodes.Count; ++n)
            {
                if (_nodes[n].Index() != Constants.INVALID_NODE_INDEX)
                {
                    ++count;
                }
            }

            return count;
        }
    }
}